package org.xiaojinlong.algo;

/**
 * @author Jin Long
 *         2015/10/28
 */
public class BST<Key extends Comparable<Key>, Value> {
    private Node<Key, Value> root;

    private static class Node<Key extends Comparable<Key>, Value> {
        private Key key;
        private Value val;
        private Node<Key, Value> left, right;
        private int N;

        public Node(Key key, Value val, int N) {
            this.key = key;
            this.val = val;
            this.N = N;
        }
    }

    public int size() {
        return size(root);
    }

    private int size(Node<Key, Value> node) {
        if (node == null)
            return 0;
        else
            return node.N;
    }

    public void put(Key key, Value val) {
        root = put(root, key, val);
    }

    private Node<Key, Value> put(Node<Key, Value> x, Key key, Value val) {
        if (x == null)
            return new Node<>(key, val, 1);

        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            x.left = put(x.left, key, val);
        else if (cmp > 0)
            x.right = put(x.right, key, val);
        else
            x.val = val;

        x.N = size(x.left) + size(x.right) + 1;

        return x;
    }
}
